package leetcode.editor.cn;
import java.util.HashMap;
import java.util.Map;
//输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
//输出：[1,2,3,4,5,6,7]
public class TestTree {
    Map<Integer, Integer> posMap;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        posMap = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            posMap.put(postorder[i], i);
        }
        return constructTree(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
    }

    /**
     *
     * @param preOrder 前序数组
     * @param pl 前序数组左指针
     * @param pr 前序数组右指针
     * @param postOrder 后续数组
     * @param ppl 后序数组左指针
     * @param ppr 后序数组右指针
     * @return
     */
    private TreeNode constructTree(int[] preOrder, int pl, int pr, int[] postOrder, int ppl, int ppr) {
        if (pl > pr || ppl > ppr) {
            return null;
        }
        TreeNode root = new TreeNode(preOrder[pl]);
        if (pl == pr || ppl == ppr) {
            return root;
        }
        int pos = posMap.get(preOrder[pl + 1]);
        root.left = this.constructTree(preOrder, pl + 1, pl + pos - ppl + 1, postOrder, ppl, pos);
        root.right = this.constructTree(preOrder, pl + pos - ppl + 2, pr, postOrder, pos + 1, ppr - 1);
        return root;
    }


}
